import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Hashtable;
import java.util.Scanner;
import java.util.Vector;

/*
 * Created by Jesse Phillips
 * Created on Feb 25, 2006
 */
/**
 * This class will grab input from a text file, convert
 * equations in infixed form postfix form and then evaluate
 * the equation.
 * 
 * <p><b>
 * Extra Credit:
 * </b><pre>
 * Attempted extra credit not yet stated.
 * </pre><b>
 * 
 * History:
 * </b><pre>
 * Feb 25, 2006: Project started. Ported code from D,
 * 			(ArrayQueue, LinkedStack, Node)
 * Feb 27, 2006: Ported more code from D, (ArrayStack)
 * Feb 28, 2006: Ported code from D, (PostfixDriver)
 * March 1, 2006: Added comments
 * </pre>
 * 
 * @author Jesse Phillips
 * @see "My implementation of Postfix writen in D"
 */
public class PostfixDriver {
	Scanner input;
	ArrayQueue post;
	ArrayStack stack;
	Hashtable key;
	Vector<String> expr;
	Vector<String> postfixed;
	PrintWriter output;

	public static void main(String[] args) {
		System.out.println("Loading application...");
		PostfixDriver program = new PostfixDriver("P4Input.txt");
		program.run();
		System.out.println("Printing to file P4Output.txt");
		System.out.println("Leaving application");
		 //answers
			// AC+D*
			// ACD*+
			// ABC^^DE*-
			// // ABCDE*
			// AB/C*D-
			// ED-BAC*+B-+
	}
	
	/**
	 * Grabs the needed information from the file
	 * to run the equation solver.
	 * 
	 * @param file The input file to read
	 */
	public PostfixDriver(String file) {
		try {
			input = new Scanner(new File(file));
			output = new PrintWriter(new FileWriter("P4Output.txt"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			System.exit(1);
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(1);
		}
		post = new ArrayQueue(100);
		key = new Hashtable();
		stack = new ArrayStack(100);
		postfixed = new Vector<String>();
		
		buildKey();
		buildExpr();
	}
	
	/**
	 * Converts, solves, and prints out the results from
	 * the equations.
	 */
	public void run() {
		for(String line : expr) {
			output.println("INFIX EXPRESSION:\t" + line.substring(0, line.length()-1));
			for(int j = 0; line.charAt(j) != '#'; j++)
				buildPostfix(line.charAt(j));
			String post = cleanup();
			output.println("POSTFIX EXPRESSION:\t" + post);
			output.println("EXPRESSION VALUE:\t" + solve(post));
			output.println();
		}
		output.close();
	}
	
	/**
	 * Decides what to do with the character passed in
	 * 
	 * @param oper An oper, operator or operand
	 */
	public void buildPostfix(char oper) {
//		/ Build the postfix expression from the string
		if(oper == ' ')
			;
		else if(oper == '(')
			stack.push(oper);
		else if(isOperand(oper))
			post.enque(oper);
		else if(oper == ')')
			for(char item = stack.pop(); item != '('; item = stack.pop())
				post.enque(item);
		else {
			int stackPower = compare(stack, oper);
			for( ; stackPower > 0; stackPower = compare(stack, oper))
				post.enque(stack.pop());
			stack.push(oper);
		}
	}
	
	/**
	 * Places the final touch to everything. Clears off
	 * the stack and creates the postfix string.
	 * 
	 * @return
	 */
	public String cleanup() {
		while(!stack.isEmpty()) {
			post.enque(stack.pop());
		}
		String finnish = "";
		while(!post.isEmpty()) {
			finnish += post.deque();
		}
		postfixed.addElement(finnish);
		return finnish;
	}
	
	/**
	 * Tells if the item is an operand or an operator
	 * 
	 * @param item what is to be checked
	 * @return True if it is an operand
	 */
	private boolean isOperand(char item) {
		int intItem = (int) item;
		
		return intItem > 63 && intItem < 91 ? true : false;
	}
	
	/**
	 * Compares the priority of the item and what is on
	 * the stack.
	 * 
	 * @param stack What stack we are dealing with
	 * @param item What item we are dealing with
	 * @return 1 if the stack has greater priority
	 * 		and -1 if the stack has lower priority
	 */
	private int compare(ArrayStack stack, char item) {
		if(stack.isEmpty())
			return 0;
		byte itemPower = 0;
		byte stackPower = 0;

		switch(stack.peak()) {
			case '^':
			case '/':
			case '*':
				stackPower++;
			case '-':
			case '+':
				stackPower++;
			default:
				break;
		}
		switch(item) {
			case '^':
				itemPower++;
			case '/':
			case '*':
				itemPower++;
			case '-':
			case '+':
				itemPower++;
			default:
				break;
		}

		return stackPower < itemPower ? -1 : 1;
	}
	
	/**
	 * Builds the key (A = #) from the first section of the file.
	 */
	private void buildKey() {
		for(String line = input.nextLine(); line.charAt(0) != '#'; line = input.nextLine()) {
			key.put(line.charAt(0), line.substring(2,line.length()));
		}
	}
	
	/**
	 * Puts all the infixed expressions into a vector.
	 */
	private void buildExpr() {
		expr = new Vector<String>();
		while(input.hasNext()) {
			String line = input.nextLine();
			if(line.charAt(0) == '#')
				break;
			expr.addElement(line);
		}
	}
	
	/**
	 * Solves any given postfix equation.
	 * 
	 * @param expr what is to be solved must be in postfix form.
	 * @return the resulting value.
	 */
	private double solve(String expr) {
		LinkedStack stack = new LinkedStack();
		for(int i = 0; i < expr.length(); i++)
			if(isOperand(expr.charAt(i)))
				stack.push((Double.valueOf((String)key.get(expr.charAt(i)))).doubleValue());
			else {
				double b = stack.pop();
				double a = stack.pop();
				double answer;
				switch(expr.charAt(i)) {
				case '+':
					answer = a + b;
					break;
				case '-':
					answer = a - b;
					break;
				case '*':
					answer = a * b;
					break;
				case '/':
					answer = a / b;
					break;
				case '^':
					answer = Math.pow(a, b);
					break;
				default:
					answer = 0;
					break;
				}
				stack.push(answer);
			}
		
		return stack.pop();
	}
}